<?php
include_once "init.php";
include_once "func/print.php";

//表示一个图的邻接表
$adjacent_list=[
    1=>[2,6,8],
    2=>[3,4],
    3=>[4,8],
    4=>[5,7],
    5=>[6,8],
    6=>[7,8],
    7=>[8],
    8=>[],
];
//表示另一个图的邻接矩阵，省略了不邻接的顶点
$adjacent_matrix=[
    1=>[2=>1,3=>1,4=>10],
    2=>[4=>1,5=>1],
    3=>[6=>1],
    4=>[3=>1,6=>1,7=>1],
    5=>[4=>1,7=>1],
    6=>[],
    7=>[6=>1],
];

$graph=new DirectedAcyclicGraph();
$graph->initWithAdjacencyList($adjacent_list);

/**
 * 拓扑排序
 */
$result=$graph->getTopologySortList();
foreach($result as $vertex){
    echo $vertex->no."\t";
}
echo "\r\n";

$result=$graph->getTopologySortList2();
foreach($result as $vertex){
    echo $vertex->no."\t";
}
echo "\r\n";

/**
 * 无权最短路径
 */
$result=$graph->unweighted($graph->list[1]);
echo "每个节点距离1号节点的距离\r\n";
print_vertex_list_distance($result);
$result=$graph->unweighted2($graph->list[2]);
echo "每个节点距离2号节点的距离\r\n";
print_vertex_list_distance($result);

/**
 * 加权最短路径
 */
$result=$graph->dijkstra($graph->list[3]);
print_vertex_list_distance($result);

$graph->initWithAdjacencyMatrix($adjacent_matrix);
$result=$graph->dijkstra($graph->list[1]);
print_vertex_list_distance($result);
$result=$graph->dijkstra($graph->list[2]);
print_vertex_list_distance($result);
$result=$graph->dijkstra($graph->list[3]);
print_vertex_list_distance($result);

function print_vertex_list_distance($list)
{
    /** @var Vertex $vertex */
    foreach($list as $vertex){
        echo "编号:{$vertex->no}\t";
        $adjacent_no=[];
        foreach($vertex->adjacent as $adjacent_vertex){
            $adjacent_no[]=$adjacent_vertex->no;
        }
        echo "邻接节点:".implode(",",$adjacent_no)."\t";
        echo "距离:{$vertex->distance}\t";
        if($vertex->previous){
            echo "上个节点:{$vertex->previous->no}\t";
        }
        echo "\r\n";
    }
    echo "\r\n";
}
